home *** CD-ROM | disk | FTP | other *** search
/ Network CD 1 / Network CD.iso / fredfish / 921-930 / ff926 / treetool / treetool.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-06  |  11.6 KB  |  292 lines
  1. /* -------------------------------------------------------------  */
  2. /* TreeTool.c                                                     */
  3. /* -------------------------------------------------------------  */
  4. /*                                                                */
  5. /* Function:  Provides basic functions to work with non-balanced  */
  6. /*            , acyclic trees, in a structure independant way.    */
  7. /*                                                                */
  8. /*     Note: This code is public-domain, you can do wathever you  */
  9. /*           want with it. But, I would like to know if you're    */
  10. /*           using it somewhere.                                  */
  11. /*                                                                */
  12. /* History:                                                       */
  13. /*                                                                */
  14. /* 1.0: Summer 1993: Jean-Christophe Clement (Initial release)    */
  15. /*                                                                */
  16. /* -------------------------------------------------------------  */
  17.  
  18. #include <stdio.h>
  19. #include <string.h>
  20. #include <stdlib.h>
  21. #include "TreeTool.h"
  22.  
  23. void iKillNodes(NODE_HANDLE,void (*)() );
  24. void iApplyFunction(NODE_HANDLE, void (*)());
  25.  
  26. extern int main();
  27.  
  28. /* -------------------------------------------------------------  */
  29. /* tt_NewNode                                                     */
  30. /*                                                                */
  31. /* Function: Allocate memory for a new node. Will make the new    */
  32. /*           node a son of the node 'nodeHandle'. Pointer to      */
  33. /*           user data is kept.                                   */
  34. /*     Note: If NULL is passed as 'nodeHandle', the function      */
  35. /*           will return a node linked to nothing (Be aware to    */
  36. /*           use it carefully). If NULL is passed as 'data', a    */
  37. /*           NULL data pointer will be put in the node but the    */
  38. /*           node will be created.                                        */
  39. /*           Return NULL is no new node has been allocated.       */
  40. /* -------------------------------------------------------------  */
  41. NODE_HANDLE tt_NewNode(NODE_HANDLE nodeHandle,void *data)
  42. {
  43.   NODE_HANDLE newNode=NULL;
  44.   NODE_HANDLE tempNode=NULL;
  45.  
  46.   if( newNode = (NODE_HANDLE) malloc(sizeof(struct node)) )
  47.   {
  48.     newNode->data=data;
  49.     newNode->NextNode=NULL;
  50.     newNode->FirstLeftSon=NULL;
  51.  
  52.     if( nodeHandle == NULL )
  53.     { /* Create an unlinked node. */
  54.       newNode->PreviousNode=NULL;
  55.     }
  56.     else
  57.     { /* Create a node linked to the one passed */
  58.  
  59.       tempNode=tt_GetLastSon(nodeHandle);
  60.       if(tempNode)
  61.       { /* Add another son. */
  62.         tempNode->NextNode=newNode;
  63.         newNode->PreviousNode=tempNode;
  64.       }
  65.       else
  66.       { /* Add the first son. */
  67.         newNode->PreviousNode=nodeHandle;
  68.         nodeHandle->FirstLeftSon=newNode;
  69.       }
  70.     }
  71.   }
  72.   return(newNode);
  73. }
  74.  
  75. /* Function that kills all the same level and sub-level nodes from */
  76. /* the passed node (included in the deletion).                     */
  77. void iKillNodes(NODE_HANDLE nodeHandle,void (*killFunc)())
  78. {
  79.   if(nodeHandle)
  80.   {
  81.     iKillNodes(nodeHandle->FirstLeftSon,killFunc);
  82.     iKillNodes(nodeHandle->NextNode, killFunc);
  83.     if(nodeHandle->data && killFunc) (*killFunc)(nodeHandle->data);
  84.     free(nodeHandle);
  85.   }
  86. }
  87.  
  88. /* -------------------------------------------------------------  */
  89. /* tt_KillNode                                                    */
  90. /*                                                                */
  91. /* Function: Deallocate all the memory for the specified node     */
  92. /*           and all of it's child's node memory. Frees data      */
  93. /*           too using the passed function (of course, we         */
  94. /*           assume that the client will de-allocate the data        */
  95. /*           correctly!)                                                  */
  96. /*     Note: nil.                                                 */
  97. /* -------------------------------------------------------------  */
  98. void tt_KillNode(NODE_HANDLE nodeHandle, void (*killFunc)() )
  99. {
  100.   if(nodeHandle)
  101.   {
  102.     if(nodeHandle->PreviousNode) /* Watch if we are not on top of the tree. */
  103.     {
  104.       if(nodeHandle->NextNode)
  105.       { /* If there is at least another node on the same level, it should */
  106.         /* now points on the previous node.                               */
  107.         nodeHandle->NextNode->PreviousNode=nodeHandle->PreviousNode;
  108.       }
  109.       if(nodeHandle->PreviousNode->FirstLeftSon == nodeHandle)
  110.       { /* If the first left son is deleted, the father should point to the */
  111.         /* new one.                                                         */
  112.         nodeHandle->PreviousNode->FirstLeftSon = nodeHandle->NextNode;
  113.       } else nodeHandle->PreviousNode->NextNode=nodeHandle->NextNode;
  114.     }
  115.     iKillNodes(nodeHandle->FirstLeftSon,killFunc); /* Kill the sub-nodes. */
  116.  
  117.     /* Deallocate the current node (data and node). */
  118.     if(nodeHandle->data && killFunc) (*killFunc)(nodeHandle->data);
  119.     free(nodeHandle);
  120.   }
  121. }
  122.  
  123. /* -------------------------------------------------------------  */
  124. /* tt_GetLeftBrother                                              */
  125. /*                                                                */
  126. /* Function: Returns the left brother of the passed node if       */
  127. /*           they both exist.                                     */
  128. /*     Note: Returns NULL otherwise.                              */
  129. /* -------------------------------------------------------------  */
  130. NODE_HANDLE tt_GetLeftBrother(NODE_HANDLE nodeHandle)
  131. {
  132.   if(nodeHandle)
  133.   {
  134.     if( nodeHandle->PreviousNode->FirstLeftSon != nodeHandle )
  135.     {
  136.       return(nodeHandle->PreviousNode);
  137.     }
  138.   };
  139.   return(NULL);
  140. }
  141.  
  142. /* -------------------------------------------------------------  */
  143. /* tt_GetRightBrother                                             */
  144. /*                                                                */
  145. /* Function: Returns the right brother of the passed node if      */
  146. /*           they both exist.                                     */
  147. /*     Note: Returns NULL otherwise.                              */
  148. /* -------------------------------------------------------------  */
  149. NODE_HANDLE tt_GetRightBrother(NODE_HANDLE nodeHandle)
  150. {
  151.   if(nodeHandle)
  152.   {
  153.     return(nodeHandle->NextNode);
  154.   } else return(NULL);
  155. }
  156.  
  157. /* -------------------------------------------------------------  */
  158. /* tt_GetSuperMariosBrother                                       */
  159. /*                                                                */
  160. /* Function: To prove that there is still place for fun in        */
  161. /*           computer sciences.                                   */
  162. /*     Note: Is harmless actually.                                */
  163. /* -------------------------------------------------------------  */
  164. void tt_GetSuperMariosBrother()
  165. {
  166.   printf("SuperMario's Brother is Luigi.\n");
  167.   printf("...and I'm really getting tired of all this Nintendo stuff.\n");
  168. }
  169.  
  170. /* -------------------------------------------------------------  */
  171. /* tt_GetFirstSon                                                 */
  172. /*                                                                */
  173. /* Function: Returns the first left son of the specified node.    */
  174. /*     Note: Returns NULL is there is not such a son.             */
  175. /* -------------------------------------------------------------  */
  176. NODE_HANDLE tt_GetFirstSon(NODE_HANDLE nodeHandle)
  177. {
  178.   if(nodeHandle)
  179.   {
  180.     return(nodeHandle->FirstLeftSon);
  181.   } else return(NULL);
  182. }
  183.  
  184. /* -------------------------------------------------------------  */
  185. /* tt_GetLastSon                                                  */
  186. /*                                                                */
  187. /* Function: Returns the rightmost son of the specified node.     */
  188. /*     Note: Returns NULL is there is no such son.                */
  189. /* -------------------------------------------------------------  */
  190. NODE_HANDLE tt_GetLastSon(NODE_HANDLE nodeHandle)
  191. {
  192.   if(nodeHandle && nodeHandle->FirstLeftSon) /* Check NULL handle passed and top of tree. */
  193.   {
  194.     nodeHandle=nodeHandle->FirstLeftSon;
  195.  
  196.     /* We go foward on the linked list until we get to the rightmost son. */
  197.     while(nodeHandle->NextNode)
  198.     {
  199.       nodeHandle=nodeHandle->NextNode;
  200.     }
  201.     return(nodeHandle);
  202.   } else return(NULL);
  203. }
  204.  
  205. /* -------------------------------------------------------------  */
  206. /* tt_GetFather                                                   */
  207. /*                                                                */
  208. /* Function: Returns the father node associated with the passed   */
  209. /*           one.                                                 */
  210. /*     Note: NULL if top of tree or NULL NODE_HANDLE.             */
  211. /* -------------------------------------------------------------  */
  212. NODE_HANDLE tt_GetFather(NODE_HANDLE nodeHandle)
  213. {
  214.   if(nodeHandle && nodeHandle->PreviousNode) /* Check NULL handle passed and top of tree. */
  215.   {
  216.     /* We go back on the linked list until we get to the first left son. */
  217.     while(nodeHandle->PreviousNode->FirstLeftSon != nodeHandle)
  218.     {
  219.       nodeHandle=nodeHandle->PreviousNode;
  220.     }
  221.     return(nodeHandle->PreviousNode);
  222.   } else return(NULL);
  223. }
  224.  
  225. /* -------------------------------------------------------------  */
  226. /* tt_SetNodeData                                                 */
  227. /*                                                                */
  228. /* Function: Will link the passed data pointer to a node.         */
  229. /*     Note: If there is already a data pointer in this node,       */
  230. /*           it will be replaced.                                          */
  231. /*           Returns a void pointer where the client              */
  232. /*           can write to modify the node content                 */
  233. /*           directly.                                            */
  234. /* -------------------------------------------------------------  */
  235. void *tt_SetNodeData(NODE_HANDLE nodeHandle,void *data)
  236. {
  237.   if(nodeHandle)
  238.   {
  239.     nodeHandle->data=data;
  240.     return(nodeHandle->data);
  241.   } else return(NULL);
  242. }
  243.  
  244. /* -------------------------------------------------------------  */
  245. /* tt_GetNodeData                                                 */
  246. /*                                                                */
  247. /* Function: Return the pointer to the user data section of the   */
  248. /*           passed node.                                                    */
  249. /*     Note: You can directly alter the content of this data ptr. */
  250. /* -------------------------------------------------------------  */
  251. void *tt_GetNodeData(NODE_HANDLE nodeHandle)
  252. {
  253.   if(nodeHandle)
  254.   {
  255.     return(nodeHandle->data);
  256.   } else return(NULL);
  257. }
  258.  
  259. /* Internal function for tt_ApplyFunction */
  260. void iApplyFunction(NODE_HANDLE nodeHandle, void (*oneFunc)())
  261. {
  262.   if(nodeHandle)
  263.   {
  264.     iApplyFunction(nodeHandle->FirstLeftSon, oneFunc );
  265.     iApplyFunction(nodeHandle->NextNode, oneFunc );
  266.  
  267.     (*oneFunc)(nodeHandle);
  268.   }
  269. }
  270.  
  271. /* -------------------------------------------------------------  */
  272. /* tt_ApplyFunction                                                            */
  273. /*                                                                                */
  274. /* Function: Apply a passed function on every node of the Tree      */
  275. /*           passed as a NODE_HANDLE.                                     */
  276. /*     Note: Custom function 'oneFunc' will receive one                */
  277. /*           parameter which will be the NODE_HANDLE of the          */
  278. /*           current node you want your function to be used on.   */
  279. /*           Function will be applied on the prefix path.         */
  280. /* -------------------------------------------------------------  */
  281. void        tt_ApplyFunction(NODE_HANDLE nodeHandle, void (*oneFunc)())
  282. {
  283.   if(nodeHandle)
  284.   {
  285.     iApplyFunction(nodeHandle->FirstLeftSon, oneFunc );
  286.   }
  287.   (*oneFunc)(nodeHandle);
  288. }
  289.  
  290.  
  291.  
  292.